import { defaultToString } from '../util';
import { ValuePair } from './models/value-pair';
import { LinkedList } from '..';

/**
 * HashTable：Dictionary类的一种散列表实现，也叫HashMap。区别就是HashTable用hash值作为键，并且可以相同key不同value
 * 分离链接法就是为散列表的每一个位置创建链表，将相同散列值存储在各自的链表中以解决冲突。
 * 这种方法虽然是最简单的处理冲突的方法，但是比较耗存储空间如果每个位置都用链表。
 * 可尝试线性探查方法，请查看hash-table-linear-probing.ts和hash-table-linear-probing-lazy.ts的两个类。
 */
export default class HashTableSeparateChaining<K, V> {
    private _toStrFn: (key: K) => string;
    private _table: { [key: string]: LinkedList<ValuePair<K, V>> };
    constructor(toStrFn: (key: K) => string = defaultToString) {
        this._table = {};
        this._toStrFn = toStrFn;
    }
    /**
     * 散列函数1
     */
    private loseloseHashCode(key: K): number {
        if (typeof key === 'number') {
            return key;
        }
        const tableKey = this._toStrFn(key);
        let hash = 0;
        for (let i = 0, le = tableKey.length; i < le; i ++) {
            hash += tableKey.charCodeAt(i);
        }
        return hash % 37;
    }
    /**
     * 散列函数2
     * 一个表现良好的散列函数由几个方面构成：
     * 插入和检索元素的时间（即性能），以及较低的冲突可能性。
     */
    /* private djb2HashCode(key: K) {
        const tableKey = this._toStrFn(key);
        let hash = 5381;
        for (let i = 0; i < tableKey.length; i ++) {
            hash = (hash * 33) + tableKey.charCodeAt(i);
        }
        return hash % 1013;
    } */
    /**
     * 得到key对应的hash值，这个hash值会作为hashtable的键
     */
    public hashCode(key: K): number {
        // return this.djb2HashCode(key); // 使用更好的散列函数
        return this.loseloseHashCode(key);
    }
    /**
     * 向HashTable中添加新元素。不同字符串可能有相同的哈希值，所以可以用链表的push方法，以防被覆盖
     */
    public put(key: K, value: V): boolean {
        if (key != null && value != null) {
            const tableKey: number = this.hashCode(key);
            let linkedList: LinkedList<ValuePair<K, V>> = this._table[tableKey];
            if (linkedList == null) { // 如果这个链表不存在就新建一个
                linkedList = new LinkedList<ValuePair<K, V>>();
                this._table[tableKey] = linkedList;
            }
            // 将新元素添加到链表尾部（不同姓名可能有相同的哈希值，直接push进去以免互相覆盖以解决冲突）
            linkedList.push(new ValuePair<K, V>(key, value));
            return true;
        }
        return false;
    }
    /**
     * 通过以键值作为参数查找对应的值并返回，但只能得到最先被添加进去的那一项
     */
    public get(key: K): V {
        if (key != null) {
            const linkedList: LinkedList<ValuePair<K, V>> = this._table[this.hashCode(key)];
            if (linkedList != null && !linkedList.isEmpty()) {
                let current = linkedList.getHead();
                while (current != null) {// 在链表里查找相同key的项，key是唯一的
                    if (current.element.key === key) {// 最先被添加，得到就立马返回不管后面还有没有相同key的项
                        return current.element.value;
                    }
                    current = current.next;
                }
            }
        }
        return undefined;
    }
    /**
     * 通过键来删除字典中对应的键值对，但只能删除最先被添加进去的那一项
     */
    public remove(key: K): boolean {
        if (key != null) {
            const tableKey: number = this.hashCode(key);
            const linkedList: LinkedList<ValuePair<K, V>> = this._table[tableKey];
            if (linkedList != null && !linkedList.isEmpty()) {
                let current = linkedList.getHead();
                while (current != null) {// 在链表里查找相同key的项，key是唯一的
                    if (current.element.key === key) {// 最先被添加，得到就立马返回不管后面还有没有相同key的项
                        linkedList.remove(current.element);
                        if (linkedList.isEmpty()) { // 删除一项检查一下linkedList是否为空
                            delete this._table[tableKey];
                        }
                        return true;
                    }
                    current = current.next;
                }
            }
        }
        return false;
    }
    /**
     * hashtable大小，把hashtable中每一个key对应的链表中所有项相加
     */
    public size(): number {
        let count = 0;
        Object.values(this._table).forEach(
            (linkedList: LinkedList<ValuePair<K, V>>) => count += linkedList.size());
        return count;
    }
    /**
     * hashtable是否为空
     */
    public isEmpty(): boolean {
        return this.size() === 0;
    }
    /**
     * 返回hashtable
     */
    public getTable(): { [key: string]: LinkedList<ValuePair<K, V>> } {
        return this._table;
    }
    /**
     * 清空hashtable
     */
    public clear() {
        this._table = {};
    }
    /**
     * 返回hashtable的字符串形式
     */
    public toString(): string {
        if (this.isEmpty()) {
            return '';
        }
        const keys = Object.keys(this._table);
        let objString = `{${keys[0].toString()} => ${this._table[keys[0]].toString()}}`;
        for (let i = 1; i < keys.length; i ++) {
            objString = `${objString},{${keys[i].toString()} => ${this._table[keys[i]].toString()}}`;
        }
        return objString;
    }
}
